package week_08;

/**
 * 680. 验证回文字符串 Ⅱ
 * 给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * 输入: s = "aba"
 * 输出: true
 * 示例 2:
 * <p>
 * 输入: s = "abca"
 * 输出: true
 * 解释: 你可以删除c字符。
 * 示例 3:
 * <p>
 * 输入: s = "abc"
 * 输出: false
 */

public class ValidPalindrome_II_680 {
    public boolean validPalindrome(String s) {
        // 只需要删一次就是回文=> 说明 双指针往中间夹时：
        // 不等时 左右各删一个字母后，递归还是回文子串
        // 说明对
        return validPalindrome(s, 0, s.length() - 1, true);
    }

    private boolean validPalindrome(String s, int start, int end, boolean isDelete) {
        while (start < end) {
            if (s.charAt(start) == s.charAt(end)) {
                start++;
                end--;
            } else if (s.charAt(start) != s.charAt(end)) {
                if (isDelete) {
                    return validPalindrome(s, start + 1, end, false) ||
                            validPalindrome(s, start, end - 1, false);
                }
                return false;
            }
        }
        return true;
    }

}
